#include <stdio.h>

#define INF 0x3f3f3f
#define MAXV 6

typedef struct Graph
{
    int n;
    int edges[MAXV][MAXV];
} Graph;

// Prim
void prim(Graph g, int v) {
// 存储最小生成树生成过程中U到V-U的最小距离，
// 其中lowcost的索引表示V-U的顶点，
// 如lowcost[2]表示V到2的最短距离，
// 具体是V中到哪个顶点，在closest中存储
    int lowcost[MAXV];
    int closest[MAXV];  // 存储最小生成树生成过程中U到V-U的最小距离对应的顶点
    int min, k;

    // 初始化lowcost和closest
    for (int i = 0; i < g.n; i++) {
        // U = {v} V-U = {其余顶点}
        lowcost[i] = g.edges[v][i];
        closest[i] = v;
    }

    // 执行n-1次循环，来找到n-1条边
    for (int count = 0; count < g.n - 1; count++) {
        min = INF;
        // 从lowcost中找出最小的边，并将边的顶点添加到V中
        for (int i = 0; i < g.n; i++) {
            if (lowcost[i] != 0 && lowcost[i] < min) {
                min = lowcost[i];
                k = i;
            }
        }
        printf("from %d to %d weiht: %d\n", closest[k], k, min);
        // 将顶点添加到V中，即将lowcost中的权重信息更新为0
        lowcost[k] = 0;

        // 找出k到V-U的最小距离，并更新lowcost和closest
        for (int i = 0; i < g.n; i++) {
            if (g.edges[k][i] != 0 && g.edges[k][i] < lowcost[i]) {
                // 更新V到i的最小距离
                lowcost[i] = g.edges[k][i];
                // 记录V到i的最小距离对应的顶点为k
                closest[i] = k;
            }
        }
    }
    // 所以最终closest记录的是最小生成树中顶点的连接关系
    // 打印closest
    for (int i = 0; i < g.n; i++) {
        printf("%2d<=>%2d\n", i, closest[i]);
    }    

}


// 构建无向图
void createGraph(Graph *g)
{
    int i, j;
    g->n = MAXV;
    int adjMatrix[MAXV][MAXV] = {
        {0, 6, 1, 5, INF, INF},
        {6, 0, 5, INF, 3, INF},
        {1, 5, 0, 5, 6, 4},
        {5, INF, 5, 0, INF, 2},
        {0, 3, 6, INF, 0, 6},
        {INF, INF, 4, 2, 6, 0}};
    for (i = 0; i < MAXV; i++)
    {
        for (j = 0; j < MAXV; j++)
        {
            g->edges[i][j] = adjMatrix[i][j];
        }
    }
}


int main()
{
    Graph g;
    createGraph(&g);
    prim(g, 0);
    return 0;
}




